package com.cskaoyan.com.generic.generic1;

import java.util.Objects;

/**
 * 使用双向链表, 实现一个数据结构为线性表的数据容器/集合类
 *
 * 集合类:
 *       1, 使用
 *       2, 底层
 *       3, 逻辑
 */
public class MyDBLinkedList<XXX> {

    private Node head; // MyDBLinkedList底层所持有的双向链表的头结点
    private Node end;  // MyDBLinkedList底层所持有的双向链表的尾结点
    private int size;  // MyDBLinkedList链表中存储的数据量


    /**
     * MyDBLinkedList的根据内容的添加方法
     * @param str: 要添加的内容
     * @return: 添加是否成功
     */
    public boolean add(XXX str){

        // 判断链表是否为空
        if (isEmpty()){
            // 新添加的内容, 既是头结点, 又是尾结点
            head = new Node(str);
            end = head;
            size++;
            return true;
        }

        Node node = new Node(str);
        node.pre = end;
        end.next = node;
        end = node;
        // 简化为
        // end.next = new Node(end, str, null);
        // end = end.next;
        size++;

        return true;
    }

    /**
     * MyDBLinkedList根据内容的删除方法
     * @param str: 要删除的内容
     * @return: 删除是否成功
     */
    public boolean remove(XXX str){
        // 判断链表是否为空
        if (isEmpty()){
            return false;
        }


        // 判断删除的是否是头结点
        if (Objects.equals(str, head.value)){
            // 删除就是头结点

            // 判断一个特殊情况: 链表只剩一个结点了
            if (size == 1){
                // 只剩一个结点, 还被删除了
                head = null;
                end = null;
            } else {
                // 剩多个
                head = head.next;
                head.pre = null;
            }
            size--;
            return true;
        }

        // 处理尾的删除
        if (Objects.equals(str, end.value)){
            // 删除就是尾结点
            end = end.pre;
            end.next = null;
            size--;
            return true;
        }

        // 删除中间某个位置的数据
        Node mid = head; // 定义一个遍历结点

        // mid的下一个结点存在, 并且下一个结点不是要查找的内容, 向后遍历
        while (mid.next != null && !Objects.equals(str, mid.next.value)){
            mid = mid.next;
        }

        // 1, 第一个跳出条件
        if (mid.next == null){
            // 链表遍历完了, 都没有找到这个要删除的内容
            return false;
        }

        // 2, 肯定是找到了这个要删除的内容, 同时mid是要删除结点的:前一个

        // 这个removeNode才是那个真正要删除的中间结点
        Node removeNode = mid.next;

        removeNode.next.pre = removeNode.pre;
        removeNode.pre.next = removeNode.next;
        size--;

        return true;
    }


    // 2个稍微复杂的方法: 根据下标的添加和修改
    // (作业)4个方法: 根据内容的查找和修改, 根据下标的查找和修改  (不改结构)


    public XXX get(int index){

        return head.value;
    }


    public int size(){
        return size;
    }
    public boolean isEmpty(){
        return size == 0;
    }

    // 双向链表的结点类型
    class Node{
        XXX value; // 值域
        Node pre;     // 前指针域
        Node next;    // 后指针域

        public Node(XXX value) {
            this.value = value;
        }

        public Node( Node pre, XXX value, Node next) {
            this.value = value;
            this.pre = pre;
            this.next = next;
        }
    }
}
